// @algorithm @lc id=457 lang=cpp 
// @title circular-array-loop


// #define print(...)
// @test([2,-1,1,2,2])=true
// @test([-1,2])=false
// @test([-2,1,-1,-2,-2])=false
// @test([-2,-3,-9])=true
#define same(i,j)   (nums[i] * nums[j] > 0)
class Solution {
public:
    bool circularArrayLoop(vector<int>& nums) {
        const int n = nums.size();
        auto next = [&](int i){
            return (i + nums[i]%n + n)%n;
        };
        for(int i=0; i<n; i++){
            if(!nums[i]) continue; // 跳过已标记点
            int slow = i, fast = next(i);
            while(slow != fast && same(slow, fast) && same(fast, next(fast))){
                slow = next(slow);
                fast = next(next(fast));
            }
            if(fast == slow && fast != next(fast) && same(fast, next(fast)))
                return true;
            // 标记已遍历过的环
            for(int m=i; same(m, next(m)); ){
                auto mark = m;
                m = next(m);
                nums[mark] = 0;
            }
        }
        return false;
    }
};